package base

/*
* @author: hjz
* @time: 2025/4/28 22:27
 */
func permute(nums []int, k int) [][]int {
	result := [][]int{}
	permuteOpt(nums, []int{}, k, &result)
	return result
}

func permuteOpt(src, tmp []int, k int, result *[][]int) {
	if len(tmp) == k {
		data := make([]int, k)
		copy(data, tmp)
		*result = append(*result, data)
		return
	}
	for i := 0; i < len(src); i++ {
		// 创建新的 src 切片，移除当前选中的元素
		newSrc := make([]int, len(src)-1)
		copy(newSrc[:i], src[:i])
		copy(newSrc[i:], src[i+1:])

		// 递归调用，继续选择下一个元素
		permuteOpt(newSrc, append(tmp, src[i]), k, result)
	}
}
func permute1(nums []int, k int) [][]int {
	result := [][]int{}
	backtrackSwap1(nums, 0, k, &result)
	return result
}

func backtrackSwap1(nums []int, start, k int, result *[][]int) {
	if start == k {
		// 复制前 k 个元素作为排列
		perm := make([]int, k)
		copy(perm, nums[:k])
		*result = append(*result, perm)
		return
	}

	for i := start; i < len(nums); i++ {
		// 交换 nums[start] 和 nums[i]
		nums[start], nums[i] = nums[i], nums[start]

		// 递归进入下一层
		backtrackSwap1(nums, start+1, k, result)

		// 回溯：恢复交换
		nums[start], nums[i] = nums[i], nums[start]
	}
}
